import java.util.ArrayList;
import java.util.List;

/**
 * 114. 二叉树展开为链表
 */
public class Solution_114 {
    /**
     * 前序遍历
     * <p>
     * 将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序
     * <p>
     * 时间复杂度：O(N)，N 为节点数
     * <p>
     * 空间复杂度：O(N)，N 为节点数
     */
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode pre = list.get(i - 1), cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }

    /**
     * 前序遍历二叉树，并将节点存入 list
     * 
     * @param root 二叉树根节点
     * @param list 用于存储二叉树节点
     */
    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        preorderTraversal(root.left, list);
        preorderTraversal(root.right, list);
    }

    public static void main(String[] args) {
        Solution_114 solution = new Solution_114();
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2, new TreeNode(3), new TreeNode(4));
        TreeNode right = new TreeNode(5, null, new TreeNode(6));
        root.left = left;
        root.right = right;
        solution.flatten(root);
    }
}
